package sort

import "fmt"

type Node struct {
	Val  int
	Next *Node
}

// 插入排序
func insertionLinkSort(head *Node) *Node {
	if head == nil || head.Next == nil {
		return head
	}

	dummy := &Node{}
	dummy.Next = head
	cur := head
	for cur != nil && cur.Next != nil {
		if cur.Val <= cur.Next.Val {
			cur = cur.Next
		} else {
			temp := cur.Next
			cur.Next = cur.Next.Next

			pre := dummy
			for pre.Next.Val <= temp.Val {
				pre = pre.Next
			}
			temp.Next = pre.Next
			pre.Next = temp
		}
	}
	return dummy.Next
}

// 冒泡排序
func bubbleLinkSort(head *Node) *Node {
	if head == nil || head.Next == nil {
		return head
	}

	for end := head; end.Next != nil; end = end.Next {
		for cur := head; cur.Next != end; cur = cur.Next {
			if cur.Val > cur.Next.Val {
				cur.Val, cur.Next.Val = cur.Next.Val, cur.Val
			}
		}
	}
	return head
}

// 选择排序
func selectionLinkSort(head *Node) *Node {
	if head == nil || head.Next == nil {
		return head
	}

	dummy := &Node{Next: head}
	for cur := dummy; cur.Next != nil; cur = cur.Next {
		min := cur
		for selectNode := cur; selectNode.Next != nil; selectNode = selectNode.Next {
			if selectNode.Next.Val < min.Next.Val {
				min = selectNode
			}
		}
		if min != cur {
			min.Next, cur.Next, cur.Next.Next = cur.Next, min.Next, cur.Next.Next
		}
	}
	return dummy.Next
}

func printList(head *Node) {
	for head != nil {
		fmt.Print(head.Val, " ")
		head = head.Next
	}
	fmt.Println()
}
